﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    //动态规划：dp[i][j]表示str1[0...i]与str2[0...j]的最长公共子序列
    //动态转移方程：str1[i] == str2[j] dp[i][j] = dp[i-1][j-1] + 1在i前面的最长公共子序列再加一
    //            str1[i]  != str2[j] dp[i][j] = max(dp[i-1][j],dp[i][j-1]) 删除一个元素
    //初始化：多开一行一列，dp[i][0] = 0,dp[0][i] = 0
    //填表顺序：从左往右，从上到下
    //返回值：dp[n][m]

    int n = 0, m = 0;
    cin >> n >> m;

    string str1, str2;
    cin >> str1 >> str2;

    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i < n + 1; ++i)
    {
        for (int j = 1; j < m + 1; ++j)
        {
            if (str1[i - 1] == str2[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    cout << dp[n][m] << endl;
    return 0;
}

/*
给定两个字符串 s1 和 s2，长度为 n 和 m  。求两个字符串最长公共子序列的长度。
所谓子序列，指一个字符串删掉部分字符（也可以不删）形成的字符串。
例如：字符串 "arcaea" 的子序列有 "ara" 、 "rcaa" 等。
但 "car" 、 "aaae" 则不是它的子序列。
所谓 s1 和 s2 的最长公共子序列，即一个最长的字符串，它既是 s1 的子序列，
也是 s2 的子序列。

数据范围 :
1≤m,n≤1000 。保证字符串中的字符只有小写字母。
要求：空间复杂度O(mn)，时间复杂度O(mn)
进阶：空间复杂度O(min(m,n))，时间复杂度O(mn)
输入描述：
第一行输入一个整数 n 和 m ，表示字符串 s1 和 s2 的长度。
接下来第二行和第三行分别输入一个字符串 s1 和 s2。
输出描述：
输出两个字符串的最长公共子序列的长度

示例1
输入：
5 6
abcde
bdcaaa
输出：
2
说明：
最长公共子序列为 "bc" 或 "bd" ，长度为2
*/

